package org.example.myleet.p821;

import java.util.*;

public class Solution {

    private static final int INFINITE = 10000000;

    public int[] shortestToChar(String s, char c) {
        char[] charArr = s.toCharArray();
        int[] result = new int[charArr.length];
        Arrays.fill(result, Integer.MAX_VALUE);
        int closestIndex = -charArr.length;
        for (int i = 0; i < charArr.length; ++i) {
            if (charArr[i] == c) {
                result[i] = 0;
                closestIndex = i;
            } else {
                result[i] = Math.min(result[i], i - closestIndex);
            }
        }
        closestIndex = 2 * charArr.length;
        for (int i = charArr.length - 1; i >= 0; --i) {
            if (charArr[i] == c) {
                result[i] = 0;
                closestIndex = i;
            } else {
                result[i] = Math.min(result[i], closestIndex - i);
            }
        }
        return result;
    }

//    public int[] shortestToChar(String s, char c) {
//        char[] charArr = s.toCharArray();
//        int[] result = new int[charArr.length];
//        List<Integer> indexes = new ArrayList<>(charArr.length);
//        for (int i = 0; i < charArr.length; ++i) {
//            if (charArr[i] == c) {
//                indexes.add(i);
//            }
//        }
//        if (indexes.size() < 1) {
//            return result;
//        }
//        int left = -INFINITE, j = 0, right = indexes.get(j);
//        for (int i = 0; i < charArr.length; ++i) {
//            result[i] = Math.min(i - left, right - i);
//            if (i >= right) {
//                left = right;
//                ++j;
//                if (j < indexes.size()) {
//                    right = indexes.get(j);
//                } else {
//                    right = INFINITE;
//                }
//            }
//        }
//        return result;
//    }

//    public int[] shortestToChar(String s, char c) {
//        char[] charArr = s.toCharArray();
//        int[] result = new int[charArr.length];
//        Deque<Integer> indexes = new LinkedList<>();
//        for (int i = 0; i < charArr.length; ++i) {
//            if (charArr[i] == c) {
//                indexes.offer(i);
//            }
//        }
//        if (indexes.size() < 1) {
//            return result;
//        }
//        int left = -INFINITE, right = indexes.poll();
//        for (int i = 0; i < charArr.length; ++i) {
//            result[i] = Math.min(i - left, right - i);
//            if (i >= right) {
//                left = right;
//                if (indexes.size() > 0) {
//                    right = indexes.poll();
//                } else {
//                    right = INFINITE;
//                }
//            }
//        }
//        return result;
//    }
}
